1. Field of the Invention
The present invention relates to a device and method for detecting errors in a CRC (Cyclic Redundancy Check) code, and more particularly to a device and method for detecting in a receiver any transmission errors in the CRC code, in a case that a transmitter transmits the CRC code generated by sequencing the parity bits, which are generated by using a generator polynomial in the reverse order, unlike the conventional manner, and by appending them to the message bits. The present application is based on Korean Patent Application No. 2000-66860, which is incorporated herein by reference.
Digital communication systems often use a method that adds the parity bits to the information bearing message bits to be transmitted in order to allow the receiver to detect transmission errors. In the receiver, the parity bits are checked alone or together with the message bits to determine whether transmission errors have occurred. Among the error detection methods using such parity bits, the CRC method is known as the most powerful method.
2. Description of the Related Art
FIG. 1 illustrates the structure of the conventional CRC (Cyclic Redundancy Check) code. Referring to FIG. 1, n bits of CRC code comprise k message bits (mkxe2x88x921xcx9cm0) and nxe2x88x92k parity bits (pnxe2x88x92kxe2x88x921xcx9cP0).
The CRC code can be represented by a certain polynomial, and the parity bits can also be represented by a polynomial using the remainder polynomial of the message bit polynomial divided by the generator polynomial.
The polynomial representation of the k message bits is
m(X)=m0+m1X1+m2X2+. . . +mkxe2x88x921Xkxe2x88x921
and, the polynomial representation of the generator polynomial for generating the parity bits is
g(X)=g0+g1X1+g2X2+. . . +gnxe2x88x92kXkxe2x88x921
and, the polynomial representation of the nxe2x88x92k parity bits is
p(X)=P0+p1X1+p2X2+. . . +Pnxe2x88x92kxe2x88x921Xnxe2x88x92kxe2x88x921
Then, the CRC code can be expressed by
c(X)=Xnxe2x88x92km(X)+p(X)
where, p(X)=Xnxe2x88x92km(X) mod g(X).
Such a CRC code method for detecting whether transmission errors have occurred divides the received CRC code by the generator polynomial and detects whether the remainder of the division is zero. This method for detecting transmission errors of the CRC code can be proved by the following equations.
As stated above, since p(X) is the remainder of Xnxe2x88x92km(X) divided by g(X), the following equation can be defined.
Xnxe2x88x92km(X)=g(X)Q(X)+p(X)
Transposing p(X) to the left side, we have
Xnxe2x88x92km(X)xe2x88x92p(X)=g(X)Q(X).
Here, since xe2x80x9cxe2x88x92p(X)xe2x80x9d equals xe2x80x9c+p(X)xe2x80x9d in the operations in the binary Galois Field unlike the general operations,
Xnxe2x88x92km(X)+p(X)=g(X)Q(X).
In the above equation, since the left side equals c(X), the quotient and the remainder of c(X) divided by g(X) are Q(X) and xe2x80x9c0,xe2x80x9d respectively. FIG. 2 illustrates a conventional device for detecting CRC code error using the stated principle. Referring to FIG. 2, the related device comprises a division unit 11 for dividing the received CRC code by the generator polynomial and a decision unit 13 for deciding the occurrence of errors by using the outputs from the division unit 11. The division unit 11 comprises nxe2x88x92k one bit registers 11a, nxe2x88x92k multipliers 11b, and nxe2x88x92k exclusive-OR gates 11c. The decision unit 13 comprises a NOR gate 13a for NOR operation on the outputs from the registers 11a of the division unit 11.
When a transmitter in the digital communication system transmits the CRC code bits (mkxe2x88x921, mkxe2x88x922, . . . , m0, Pnxe2x88x92kxe2x88x921, . . . , p0) having the structure shown in FIG. 1, the CRC code bits that have passed a proper channel are input to the registers 11a sequentially and each of the CRC code bits in the registers are shifted one position from left to right with every input. And, the multipliers 11b multiply the CRC code bits sequentially transferred via the right most register 11a by coefficient signal g0, g1, g2, . . . , gnxe2x88x92kxe2x88x921 of the generator polynomial, and each of the X-OR gates 11c performs bitwise exclusive OR operation on each resultant bit from each of the multipliers 11b and each of the CRC code bits that is subsequently input. After all the n bits are input to the registers 11a and processed by the aforementioned operations, the final remainder of the CRC code divided by the generator polynomial remain in the registers 11a. If no transmission errors have occurred, all the resultant contents of the registers 11a become xe2x80x9c0s.xe2x80x9d Thus, the decision unit 13a for performing NOR operations on the nxe2x88x92k input bits from the registers 11a provides an output xe2x80x9c1,xe2x80x9d only if the CRC code has no transmission errors. On the other hand, if the result of the entire NOR operations is xe2x80x9c0,xe2x80x9d the decision unit 13a decides that the CRC code has transmission errors.
Recently, a new method to generate the CRC code using the parity bits differently from the aforementioned method was suggested as a data transmission method in the Universal Mobile Telecommunication System (UMTS) related to the next generation mobile telecommunication, called an IMT-2000. That is, the UMTS adopts a new method for using the parity bits generated by sequencing the remainder bits of the message bits divided by the generator polynomial in the reverse order, unlike the conventional technique.
The new method will be explained in detail in the following.
FIG. 3 illustrates a structure of the CRC code in which the parity bits are added in the reverse order. The CRC code is transmitted in a sequence of mkxe2x88x921, mkxe2x88x922, . . . , m0, p0, . . . , pnxe2x88x92kxe2x88x921. The CRC code can be expressed by a polynomial
c(X)=Xnxe2x88x92km(X)+pxe2x8axa5(X)
where, taking p(X)=Xnxe2x88x92km(X) mod g(X), pxe2x8axa5(X) is defined as
pxe2x8axa5(X)=Xdeg p(X)p(Xxe2x88x921).
However, the conventional error detection device can detect errors only in the conventional CRC code in which the parity bits are added in the normal order as illustrated in FIG. 1. The conventional error detection device cannot detect transmission errors in the new CRC code in which the parity bits are added in the reverse order as illustrated in FIG. 3, because the remainder of the new CRC code polynomial c(X) divided by the generator polynomial g(X) does not become xe2x80x9c0xe2x80x9d in the conventional device. Accordingly, a need exists for detecting the transmission errors in the CRC code having the reverse ordered parity bits.
The object of the present invention is to provide a device and method for detecting transmission errors of the received CRC code in which a parity bit stream is added in reverse order.
In accordance with one aspect of the present invention to accomplish the object, there is provided a device for detecting errors in the CRC code comprising a switch unit for sequentially receiving the CRC code having message bits and reverse ordered parity bits appended to the message bits and for switching the message bits and the parity bits to be transferred separately; a division unit for receiving the message bits transferred via said switch unit and for dividing the message bits by a parity bit generator polynomial to obtain a remainder; a buffer unit for receiving the parity bits transferred via said switch and for buffering the parity bits sequentially; a comparison unit for comparing the remainder bits from said division unit with the parity bits from said buffer unit; and a decision unit for deciding whether transmission errors have occurred in the CRC code on the basis of the results from said comparison unit.
The comparison unit preferably comprises a plurality of X-OR gates for comparing the remainder bits with the parity bits.
In another aspect of the present invention, there is provided a method for detecting errors in the CRC code comprising the steps of receiving CRC code having message bits and reverse ordered parity bits appended to the message bits; dividing the message bits by a parity bit generator polynomial to form a remainder; buffering the parity bits sequentially; comparing the remainder bits with the sequentially buffered parity bits; and deciding whether transmission errors have occurred in the received CRC code on the basis of the results from said step of comparing.
In another aspect of the present invention, there is provided a device for detecting errors in the CRC code comprising a switch unit for sequentially receiving the CRC code having message bits and reverse ordered parity bits appended to the message bits and for switching the message bits and the parity bits to be transferred separately; a division unit for receiving the message bits transferred via said switch unit and for dividing the message bits by a parity bit generator polynomial to form a remainder and for sequentially outputting the remainder bits in the reverse order; a comparison unit for comparing the remainder bits received sequentially from said division unit with the parity bits transferred sequentially via said switch unit; and a decision unit for deciding whether transmission errors have occurred in the received CRC code on the basis of the results from said comparison unit.
The division unit preferably comprises a plurality of one bit registers serially coupled with each other for storing the remainder bits of the message bits divided by the generator polynomial; a plurality of forward shift switches for being switched to enable forward shifting of said plurality of registers until the last message bit input from said switch unit passes through said plurality of registers; and a plurality of backward shift switches for being switched to enable backward shifting of said plurality of registers so that the remainder bits stored in said plurality of registers are provided to said comparison unit sequentially.
In another aspect of the present invention, there is provided a method for detecting errors in the CRC code comprising the steps of receiving CRC code having message bits and reverse ordered parity bits appended to the message bits; dividing the message bits by a parity bit generator polynomial to form a remainder and for sequentially outputting the remainder bits in the reverse order; comparing the sequentially received reverse ordered remainder bits with the sequentially received parity bits; and deciding whether transmission error has occurred in the received CRC code on the basis of the results from said step of comparing.
In another aspect of the present invention, there is provided a device for detecting errors in the CRC code comprising a division unit that receives and shifts input CRC code sequentially by using a plurality of one bit registers, wherein said input CRC code comprises message bits and reverse ordered parity bits appended to the message bits, and divides the message bits by a parity bit generator polynomial to form a remainder, and stores the remainder bits in said plurality of one bit registers; a comparison unit for comparing symmetrically paired two counterpart bits, from the two outermost bits to two innermost bits, of the remainder sequence stored in said plurality of registers with each other; and a decision unit for deciding whether transmission error has occurred in the input CRC code on the basis of the results from said comparison unit.
The comparison unit preferably comprises a plurality of X-OR gates, the number of which is as many as the integer part of the quotient of the division of the number of said plurality of registers by 2. If the number of said plurality of registers is odd, the center bit of the remainder stored in the center register of said plurality of registers is input directly to the decision unit.
In another aspect of the present invention, there is provided a method for detecting errors in the CRC code comprising the steps of receiving the input CRC code sequentially, wherein said input CRC code comprises message bits and reverse ordered parity bits appended to the message bits, and dividing the message bits by a parity bit generator polynomial to form a remainder; comparing symmetrically paired two counterpart bits, from the two outermost bits to the two innermost bits, of the remainder bits sequence with each other; and deciding whether transmission error has occurred in the input CRC code on the basis of the results from said step of comparing.